/**
 * 遇到括号{([就压栈
 * 遇到右括号})]就判断栈顶，匹配则出栈
 * 最后判断length是否为0
 * 
 * 时间复杂度O(n)，空间复杂度O(n)
 */ 

/**
 * @description: 判断左右括号是否匹配
 * @param {string} left
 * @param {string} right
 * @return {*}
 */
function isMatch (left: string, right: string): boolean {
  if (left === '{' && right === '}') return true
  if (left === '[' && right === ']') return true
  if (left === '(' && right === ')') return true
  return false
}

function matchBracket(str: string): boolean {
  const length = str.length
  if (length === 0) return true
  const stack: string[] = []
  const leftSymbols = '{[('
  const rightSymbols = '}])'

  for (let i = 0; i < length; i++) {
    const s = str[i]
    if (leftSymbols.includes(s)) {
      // 左括号，压栈
      stack.push(s)
    } else if (rightSymbols.includes(s)) {
      // 右括号，判断栈顶（是否出栈）
      const top = stack[stack.length - 1]
      if (isMatch(top, s)) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}